The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and shares routing information among other nodes of a network. Border Gateway Protocol (BGP) is a common protocol used to exchange routing information between subnetworks within the network. BGP is an inter-Autonomous System routing protocol. One version of it is described in A BORDER GATEWAY PROTOCOL 4 (BGP-4), RFC 1771, IETF, March 1995, which is hereby incorporated by reference. Another version is described in A BORDER GATEWAY PROTOCOL 4 (BGP-4), draft-ietf-idr-bgp4-22, IETF working draft, October 2003, which is hereby incorporated by reference. Some other documents which describe aspects of Border Gateway Protocol include: BGP COMMUNITIES ATTRIBUTE, RFC 1997, IETF, August 1996; CAPABILITIES ADVERTISEMENT WITH BGP-4, RFC 3392, IETF, November 2002; and BGP Extended Communities Attribute, draft-ietf-idr-bgp-ext-communities-06, IETF working draft, August 2003; with all of these documents being hereby incorporated by reference.
A primary function of a BGP speaking system is to exchange network reachability information with other BGP systems. This network reachability information includes information on the list of Autonomous Systems (ASs) that reachability information traverses. This information is sufficient to construct a graph of AS connectivity from which routing loops may be pruned and some policy decisions at the AS level may be enforced. To characterize the set of policy decisions that can be enforced using BGP, one must focus on the rule that a BGP speaker advertise to its peers (other BGP speakers which it communicates with) in neighboring ASs only those routes that it itself uses. Note, an Autonomous System typically refers to a set of routers under a single technical administration, using an interior gateway protocol and common metrics to route packets within the AS, and using an exterior gateway protocol to route packets to other ASs. It has also become common for a single AS to use several interior gateway protocols and sometimes several sets of metrics within an AS.
Communicating nodes initially exchange their entire BGP routing table, and then send incremental updates as the routing tables change. BGP does not require periodic refresh of the entire BGP routing table. Therefore, a BGP speaker must retain the current version of the entire BGP routing tables of all of its peers for the duration of the connection. KeepAlive messages are sent periodically to ensure the liveness of the connection. Notification messages are sent in response to errors or special conditions. If a connection encounters an error condition, a notification message is sent, the connection is closed and the routes associated with the connection are withdrawn from the routing tables.
A route may be viewed as a unit of information that pairs a destination with the attributes of a path to that destination. For example, a route may be considered to be one or more Network Layer Reachability Information (NLRI), which are associated with one set of path attributes.
Routes are advertised between a pair of BGP speakers in Update messages, with the destination being the systems whose IP addresses are reported in the Network Layer Reachability Information (NLRI) field of the Update message, and the path is the information reported in the path attributes fields of the same Update message. Routes are stored in the Routing Information Bases (RIBs): namely, the Adj-RIBs-In, the Loc-RIB, and the Adj-RIBS-Out. Routes that will be advertised to other BGP speakers must be present in the Adj-RIB-Out; routes that will be used by the local BGP speaker must be present in the Loc-RIB, and the next hop for each of these routes must be present in the local BGP speaker's forwarding information base; and routes that are received from other BGP speakers are present in the Adj-RIBs-In.
If a BGP speaker chooses to advertise a route, it may add to or modify the path attributes of the route before advertising it to a peer. BGP provides mechanisms by which a BGP speaker can inform its peer that a previously advertised route is no longer available for use. There are three methods specified in RFC 1771 by which a given BGP speaker can indicate that a route has been withdrawn from service: the IP prefix that expresses destinations for a previously advertised route can be advertised in the withdrawn routes field in the Update message, thus marking the associated route as being no longer available for use; a replacement route with the same Network Layer Reachability Information can be advertised; and the BGP speaker to BGP speaker connection can be closed, which implicitly removes from service all routes which the pair of speakers had advertised to each other.
An Update message is used to advertise a single feasible route to a peer, or to withdraw multiple unfeasible routes from service. An Update message may simultaneously advertise a feasible route and withdraw multiple unfeasible routes from service. The Update message always includes the fixed-size BGP header, and can optionally include other fields including: Unfeasible Routes Length, Withdrawn Routes, Total Path Attribute Length, Path Attributes, and Network Layer Reachability Information.
The Unfeasible Routes Length field indicates the total length of the Withdrawn Routes field in octets.
The Withdrawn Routes field is a variable length field that contains a list of IP address prefixes for the routes that are being withdrawn from service. Each IP address prefix is encoded as a two-tuple of the form <length, prefix>, with the Length field indicating the length in bits of the IP address prefix, with a length of zero indicating a prefix that matches all IP addresses (with prefix, itself, of zero octets); and the Prefix field containing IP address prefixes followed by enough trailing bits to make the end of the field fall on an octet boundary. Note that the value of trailing bits is irrelevant.
The Total Path Attribute Length includes an unsigned integer indicating the total length of the Path Attributes field in octets. Its value must allow the length of the Network Layer Reachability field to be determined as specified below. A value of 0 indicates that no Network Layer Reachability Information field is present in this Update message.
The Path Attributes is a variable length sequence of path attributes and is present in every Update. Each path attribute is a triple <attribute type, attribute length, attribute value> of variable length.
The Network Layer Reachability Information field is a variable length field containing a list of IP address prefixes.
An Update message can advertise at most one route, which may be described by several path attributes. All path attributes contained in a given Update messages apply to the destinations carried in the Network Layer Reachability Information field of the Update message.
An Update message can list multiple routes to be withdrawn from service. Each such route is identified by its destination (expressed as an IP prefix), which unambiguously identifies the route in the context of the BGP speaker—BGP speaker connection to which it has been previously been advertised. An Update message may advertise only routes to be withdrawn from service, in which case it will not include path attributes or Network Layer Reachability Information. Conversely, it may advertise only a feasible route, in which case the Withdrawn Routes field need not be present.
If the Update message contains a non-empty Withdrawn Routes field, the previously advertised routes whose destinations (expressed as IP prefixes) are contained in this field shall be removed from the Adj-RIB-In. This BGP speaker shall run its Decision Process since the previously advertised route is no longer available for use.